#define _CRT_SECURE_NO_WARNINGS 1

class MapSum {
public:
    MapSum()
    { }

    void insert(string key, int val)
    {
        if (_strValMap.count(key) == 0)
        {
            CreateMap(key, val);
        }
        else
        {
            ModifyMap(key, val);
        }
    }

    int sum(string prefix)
    {
        return _preValMap[prefix];
    }

private:
    void CreateMap(const std::string& key, int val)
    {
        _strValMap[key] = val;

        std::string prev;
        for (const char ch : key)
        {
            prev += ch;
            _preValMap[prev] += val;
        }
    }

    void ModifyMap(const std::string& key, int val)
    {
        int ori = _strValMap[key];
        int diff = val - ori;

        std::string prev;
        for (const char ch : key)
        {
            prev += ch;
            _preValMap[prev] += diff;
        }

        _strValMap[key] = val;
    }

    std::unordered_map<std::string, int> _strValMap;
    std::unordered_map<std::string, int> _preValMap;
};

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum* obj = new MapSum();
 * obj->insert(key,val);
 * int param_2 = obj->sum(prefix);
 */